BZOJ 3144 切糕

Description


Input

第一行是三个正整数P,Q,R,表示切糕的长P、 宽Q、高R。第二行有一个非负整数D,表示光滑性要求。接下来是R个P行Q列的矩阵,第z个 矩阵的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R)。
100%的数据满足P,Q,R≤40,0≤D≤R,且给出的所有的不和谐值不超过1000。

Output

仅包含一个整数,表示在合法基础上最小的总不和谐值。

Sample Input

2 2 2
1
6 1
6 1
2 6
2 6

Sample Output

6

Hint

最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1

Solution

从S向底面连边,顶面向T连边,相邻两层直接连,流量就是v[i][j][k]的权值
应该是一个比较显然的最小割模型
然后关键在于选的点差不能超过d
思考一下从k+d向k连一条INF的边就可以解决这个问题
(这道题其实我写了三天……
第一天下午写完,WA了,改不出来
第二天思考怎么改
第三天重新处理了一下思路,跟对拍程序刚正面,然后调出来了
果然还是人太弱……)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>

#define maxd 40+5
#define maxn 66000+5
#define maxm 300000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct sides{
int u,v,c;
int next;
}s[maxm];

queue<int> q;
int first[maxn],cur[maxn],ind;
int v[maxd][maxd][maxd],h[maxn];
int P,Q,R,d,S,T,ans;
int st[2][4]={{1,0,-1,0},{0,1,0,-1}};

int hash(int x,int y,int z)
{

return x*P*Q+y*Q+z;
}

void insert(int u,int v,int c)
{

s[ind]=(sides){u,v,c,first[u]},first[u]=ind++;
s[ind]=(sides){v,u,0,first[v]},first[v]=ind++;
}

bool bfs()
{

set(h,-1),h[T]=0;
q.push(T);
while( !q.empty() ){
int sd=q.front();q.pop();
for(int i=first[sd];i!=-1;i=s[i].next)
if( s[i^1].c>0 && h[s[i].v]==-1 ){
h[s[i].v]=h[sd]+1;
q.push(s[i].v);
}
}
return h[S]!=-1;
}

int dfs(int x,int flow)
{

if( x==T ) return flow;
int used=0;
for(int &i=cur[x];i!=-1;i=s[i].next)
if( h[s[i].v]+1==h[x] && s[i].c>0 ){
int w=dfs(s[i].v,min(s[i].c,flow-used));
s[i].c-=w,s[i^1].c+=w,used+=w;
if( used==flow ) return flow;
}
return used;
}

void dinic()
{

while( bfs() ){
for(int i=S;i<=T;i++)
cur[i]=first[i];
ans+=dfs(S,INT_MAX);
}
}

void init()
{

for(int i=0;i<R;i++)
for(int j=1;j<=P;j++)
for(int k=1;k<=Q;k++)
insert(hash(i,j,k),hash(i+1,j,k),v[i+1][j][k]);
for(int i=1;i<=P;i++)
for(int j=1;j<=Q;j++){
insert(S,hash(0,i,j),INT_MAX);
insert(hash(R,i,j),T,INT_MAX);
}
for(int i=1;i<=P;i++)
for(int j=1;j<=Q;j++)
for(int t=0;t<4;t++){
int sx=i+st[0][t],sy=j+st[1][t];
if( !sx || !sy || sx>P || sy>Q ) continue;
for(int k=1;k<=R;k++)
if( k+d<=R ) insert(hash(k+d,sx,sy),hash(k,i,j),INT_MAX);
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("3144.in","r",stdin);
freopen("3144.out","w",stdout);
#endif
scanf("%d%d%d%d",&P,&Q,&R,&d);
set(first,-1);
S=0,T=P*Q*R+P*Q+Q+1;
for(int i=1;i<=R;i++)
for(int j=1;j<=P;j++)
for(int k=1;k<=Q;k++)
scanf("%d",&v[i][j][k]);
init();
dinic();
printf("%d",ans);
return 0;
}